﻿#include "data_struct.h"
#include <string>
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <utility>
#include <cstdint>

#include "BlockQueue.h"

#include "BlockShaper.h"
#include "ByteBuffer.h"
#include "friend_class.h"
#include "safe_queue.h"
#include "dfsscc.h"


namespace gdface {
	inline namespace mt {
		int threadsafe_queue_test() {
			const char* usage = "I can do this.\n"
				"let's do some other things"
				"my be you are right.\n";
			threadsafe_queue<char> circle_chars;
			char* char_cursor = const_cast<char*>(usage);
			while (circle_chars.size() < 5)
			{
				circle_chars.push(*(char_cursor++));
				std::cout << "push succ.\n";
				circle_chars.wait_and_pop();
			}
			return 0;
		}
	}
}



void StructOperations::InitList(const char* list_cfg) {

	if (list_cfg == nullptr) {
		return;
	}
	ifstream is(list_cfg, ios_base::in);
	try
	{
		std::string next_token;
		while (!is.eof())
		{
			is >> std::ws;
			is >> next_token;
			if (!next_token.empty()) {
				if (list_head_ == nullptr){
					list_head_ = NewMutualNode();
					list_head_->left = nullptr;
					list_head_->right = nullptr;
					list_head_->value_ = std::atoi(next_token.c_str());
				}
				else
				{
					MutualNode* next_node = NewMutualNode();
					next_node->value_ = std::atoi(next_token.c_str());

					next_node->right = list_head_;
					list_head_->left = next_node;
					next_node->left = nullptr;
					list_head_ = next_node;
					std::cout << std::endl;

				}
			}
			is >> std::ws;
		}
		is.close();

	}
	catch (const std::exception&e)
	{
		std::cout << e.what() << std::endl;
		exit(-1);
	}
}

void StructOperations::InitTree(const char* tree_cfg) {

	if (tree_cfg == nullptr) {
		return;
	}
	ifstream is(tree_cfg, ios_base::in);
	try
	{
		std::string next_token;
		is >> std::ws;
		std::queue<MutualNode* > leaves_processed;
		leaves_processed.push(tree_root_);
		is >> std::ws;
		InitTreeRecursive(is, leaves_processed);
		DrawTree();
		is.close();
	}
	catch (const exception& e) {
		std::cout << e.what() << std::endl;
	}
}




MutualNode* StructOperations::InitTreeRecursive(istream& is, std::queue<MutualNode*>& temp_leaves) {
	
	while (! temp_leaves.empty() && ! is.eof())
	{
		if (EatWs(is)) {
			break;
		}
		MutualNode* this_root = temp_leaves.front();
		std::string next_token;
		temp_leaves.pop();
		if (this_root == nullptr ){
			this_root = NewMutualNode();
			
			
			is >> next_token;
			if (!next_token.empty()){
				this_root->value_ = std::atoi(next_token.c_str());
				tree_root_ = this_root;
			}
		}

		is >> next_token;
		if (! next_token.empty()){
			MutualNode* temp_left = NewMutualNode();
			temp_left->value_ = std::atoi(next_token.c_str());
			this_root->left = temp_left;
			temp_leaves.push(temp_left);
		}

		if (EatWs(is)) {
			break;
		}

		is >> next_token;
		if (! next_token.empty()){
			MutualNode* temp_right = NewMutualNode();
			temp_right->value_ = std::atoi(next_token.c_str());
			this_root->right = temp_right;
			temp_leaves.push(temp_right);
			
		}
		if (EatWs(is)) {
			break;
		}
	}

	return tree_root_;
	
}


void StructOperations::DrawTree() {
	if (tree_root_ == nullptr){
		return;
	}
	TraversalDFS(tree_root_);

}

void StructOperations::BinaryTree2BirectionList() {


}

void StructOperations::BirectionList2BinaryTree() {



}


void StructOperations::SortListTop2down() {

}



//////////////////////////////////////////////////////////////////////////


bool EatWs(std::istream& is) {
	std::string next_token;
	char next_char = ' ';
	while ((next_char = is.peek()) == ' ' || (next_char = is.peek()) == '\n' ||
		(next_char = is.peek()) == '\r')
	{
		is >> std::ws;
	}
	if (is.eof()) {
		return true;
	}
	return false;
}



void SortVector::InitDataFromText(const char* digital_file) {
	if (digital_file == nullptr) {
		return;
	}
	ifstream is(digital_file, ios_base::in);
	try
	{
		std::string next_token;
		while (!is.eof())
		{
			is >> std::ws;
			is >> next_token;
			if (!next_token.empty()) {
				data_.push_back(std::atoi(next_token.c_str()));
			}
			is >> std::ws;
		}
		is.close();
	}
	catch (const std::exception&e)
	{
		std::cout << e.what() << std::endl;
		exit(-1);
	}
	data_len_ = data_.size();
	internal_data_.clear();
	internal_data_.resize(data_len_);
	std::copy(data_.begin(), data_.end(), internal_data_.begin());
}


void SortVector::PrintInternalArray() {
	if (data_len_ == 0 || data_.size() == 0) {
		return;
	}

	for (size_t i = 0; i < data_.size(); i++)
	{
		std::cout << data_[i] << " ";
	}
	std::cout << std::endl;

}





void SortTest(const char* digital_file) {

	SortVector sort_manager(1024);
	sort_manager.InitDataFromText(digital_file);
	//////////////////////////////////////////////////////////////////////////
	sort_manager.InsertSort();
	sort_manager.ReInitData();
	//////////////////////////////////////////////////////////////////////////
	sort_manager.QuickSortMain();
	sort_manager.ReInitData();
	//////////////////////////////////////////////////////////////////////////
	std::vector<int>& data = sort_manager.Array();
	sort_manager.MergeSort(data);
	sort_manager.ReInitData();
	//////////////////////////////////////////////////////////////////////////
	std::cout << "Sorting algorithm testing successfully.\n";

}


void GraphAlgrithms() {
	std::cout << "Graph algorithms ...\n";
	const char*kosaraju = "kosaraju_adjacent_table.txt";
	const char* tarjan = "adjacent_table.txt";
	SCCCompute Kosaraju_compute(kosaraju);
	Kosaraju_compute.FindSccUsingKosaraju();

	SimpleFst fst;
	SCCCompute scc_finding;
	scc_finding.Tarjan_print("adjacent_table.txt");
	
}

void LeetCodeLearning(const char* usage) {
	std::cout << usage << std::endl;
	GraphAlgrithms();
	RightMove();
	FindMedianTest();
}

void FindMedianTest() {
	std::vector<int> vec1(10, 0), vec2(5, 1);
	srand(0);
	int selected_num = 0;
	while (true)
	{
		selected_num = rand();
		while (selected_num > 15)
		{
			selected_num = selected_num>> 1;
		}
		if (selected_num > 0 && selected_num < 15){
			break;
		}
	}
	FindKthofTwoUnSortedArrays(vec1, vec2, selected_num);
}


// For leetcode4
int FindMedianofTwoUnSortedArrays(std::vector<int>& array_a,
	std::vector<int>& array_b) {
	int median = 0;
	if (array_a.empty()  && array_b.empty()){
		return median;
	}

	// O((n)*log(n))
	std::vector<int> this_array = array_a, next_array = array_b;
	std::copy(next_array.begin(), next_array.end(), this_array.end());
	std::sort(this_array.begin(), this_array.end());
	int num_total_elems = this_array.size();
	if (num_total_elems % 2){
		median = (this_array[num_total_elems / 2] + this_array[num_total_elems / 2 - 1]);
	}
	else
	{
		median = this_array[(num_total_elems - 1) / 2];
	}
	// O(n)
	std::vector<int> left = array_a, right = array_b;
	std::sort(left.begin(), left.end());
	std::sort(right.begin(), right.end());
	std::vector<int> final_array(left.size() + right.size());
	while (left.size() && right.size())
	{
		if (left[left.size()-1] < right[right.size()-1]){
			final_array.push_back(right[right.size() - 1]);
			right.pop_back();
		} else{
			final_array.push_back(left[left.size() - 1]);
			left.pop_back();
		}
	}
	num_total_elems = final_array.size();
	if (num_total_elems % 2) {
		median = (final_array[num_total_elems / 2] + final_array[num_total_elems / 2 - 1]);
	}
	else
	{
		median = final_array[(num_total_elems - 1) / 2];
	}
	// O(log(n))
	std::vector<int> vec1 = array_a, vec2 = array_b;
	std::sort(vec1.begin(), vec1.end());
	std::sort(vec2.begin(), vec2.end());

	std::srand(0);
	int selected_index = rand();

	FindKthofTwoUnSortedArrays(vec1, vec2, selected_index);


	return median;
}

// We use binary search here
int FindKthofTwoUnSortedArrays(std::vector<int>& array_a,
	std::vector<int>& array_b, int kth) {
	std::string s("xbdebpqawuva");
	lengthOfLongestSubstring(s.c_str());
	LongestSubStrwithoutRepeatedChars(s);

	int a = 2, b = a & 1;
	std::vector<int> vec1 = array_a, vec2 = array_b;
	int size_vec1 = vec1.size(), size_vec2 = vec2.size(), 
		size_total = size_vec1 + size_vec2, half_size_total = size_total >> 1;
	std::sort(vec1.begin(), vec1.end());
	std::sort(vec2.begin(), vec2.end());
	if (size_total & 1){
		return FindKthSpecial(vec1, vec2, half_size_total + 1);
	}
	else {
		return (FindKthSpecial(vec1, vec2, half_size_total) + FindKthSpecial(vec1, vec2, half_size_total + 1)) / 2;
	}

	
}


int FindKthSpecial(std::vector<int>& array_a, std::vector<int>& array_b, int kth)
{
	using namespace std;
	// always assume that length(a) is equal or smaller than length(b)
	std::vector<int> vec1 = array_a, vec2 = array_b;
	int size_vec1 = vec1.size(), size_vec2 = vec2.size(),
		size_total = size_vec1 + size_vec2, half_size_total = size_total >> 1;
	if (size_vec1 > size_vec2){
	}
	if (size_vec1 == 0){
	}

	if (kth == 0){
	}
	// Dividing kth into 2 parts
	std::vector<int> selected_index(2, 0);
	int a_part = std::min(kth >> 1, size_vec1), b_part = kth - a_part;

	return 0;
}


std::string LongestSubStrwithoutRepeatedChars(std::string s) {
	using namespace std;
	string target_string = s, longest_substring;
	
	
	// Next, we use DP to solve this problem, and unorder_set should be use for storing staged information
	if (s.size() == 0) {
		return s;
	}
	if (s.size() == 1) {
		return s;
	}
	int maxSubStringLength = 1, size_english_alphabets = 256;
	int visitCharArray[256] = { s.size() };
	// all English alphabets are between 0 and 255
	for (int tmpIndex = 0; tmpIndex < 256; tmpIndex++) {
		visitCharArray[tmpIndex] = s.size();
	}

	// repeated digitals index
	int repeatPosition = 0;
	// allocating and initializing repeated string array
	int *positionArray = (int *)malloc((s.size() + 1) * sizeof(int));
	for (int tmpIndex = 0; tmpIndex <= s.size(); tmpIndex++) {
		positionArray[tmpIndex] = s.size();
	}

	for (int tmpIndex = s.size() - 1; tmpIndex >= 0; tmpIndex--) {
		int char2int = s[tmpIndex];
		repeatPosition = visitCharArray[char2int];

		// storing locations of every char
		visitCharArray[char2int] = tmpIndex;

		// the char is found
		if (repeatPosition < positionArray[tmpIndex + 1]) {
			positionArray[tmpIndex] = repeatPosition;
		}
		// the char is not found
		else {
			positionArray[tmpIndex] = positionArray[tmpIndex + 1];
		}
	}

	for (int tmpIndex = 0; tmpIndex < s.size(); tmpIndex++) {
		if (positionArray[tmpIndex] - tmpIndex > maxSubStringLength) {
			maxSubStringLength = positionArray[tmpIndex] - tmpIndex;
		}
	}
	free(positionArray);
	positionArray = nullptr;
	return s;
}


// Good solution for Leetcode 3
int lengthOfLongestSubstring(const char* s) {
	//only length of substring can be stored
	int max_lengthp = 0;
	int book[256];
	// hash 
	for (int i = 0; i < 256; i++) book[i] = 0;
	int start = 0, ending = 0, sub_start = 0, sub_end = 0;
	int length = strlen(s);
	// Only one loop can solve this problem
	while (ending < length)
	{
		if (book[(int)s[ending]] == 1)
		{
			// Find first repeated char
			// moving start cursor until s[start] == s[ending] (break)
			while (s[start] != s[ending]) book[(int)s[start++]] = 0;
			start++;
		}
		book[(int)s[ending]] = 1;
		ending++;
		if (ending - start > max_lengthp) {
			max_lengthp = ending - start;
			sub_start = start;
			sub_end = ending;
		}
	}
	max_lengthp = max_lengthp > (ending - start) ? max_lengthp : (ending - start);
	string result(s + sub_start, s + sub_end);
	if (_DEBUG){
		std::cout << "Original string : " << s << ", longest substring : " << result << std::endl;
	}
	return max_lengthp;
}

// Leetcode1, easy
vector<int> twoSum(vector<int>& nums, int target) {
	vector<int> indexes;
	return indexes;
	std::unordered_map<int, int> val2index;
	for (size_t i = 0; i < nums.size(); i++)
	{
		val2index.insert(std::pair<int, int>(nums[i], i));
	}
	for (size_t i = 0; i < nums.size(); i++)
	{
		int diff = target - nums[i];
		if (val2index.find(diff) != val2index.end()){
			indexes.push_back(i);
			indexes.push_back(val2index[i]);
			return indexes;
		}
	}
}

// For Leetcode 2
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

	return l2;
}

// Leetcode 16
int threeSumClosest(vector<int>& nums, int target) {
	// define continuous three numbers
	int closest = nums[0] + nums[1] + nums[2];
	//get difference between target and temporal sum
	int diff = abs(closest - target);
	// sort data firstly
	sort(nums.begin(), nums.end());
	for (int i = 0; i < nums.size() - 2; ++i) {
		//get the next element---->left(i+1) and the last element--->right
		int left = i + 1, right = nums.size() - 1;
		while (left < right) {
			int sum = nums[i] + nums[left] + nums[right];
			int newDiff = abs(sum - target);
			if (diff > newDiff) {
				diff = newDiff;
				closest = sum;
			}
			if (sum<target){
				++left;
			} else{
				--right;
			}
			
		}
	}
	return closest;
}


int kSumClosest(vector<int>& nums, int k,  int target) {
	int closest = 0;
	for (size_t i = 0; i < k; i++)
	{
		closest += nums[i];
	}
	int diff = abs(closest-target);
	std::sort(nums.begin(), nums.end());


	return closest;

}

//https://www.cnblogs.com/avril/p/3278873.html
int largestRectangleInHistogram() {
	int max_area = 0;
	return max_area;

}


void RightMove() {
	int64_t temp = 200;
	printf("八进制 --> %o\n", temp);
	printf("十六进制 --> %X\n", temp);
	printf("十进制 --> %d\n", temp);
	char s[512];
	itoa(temp, s, 2);
	printf("二进制 --> %s\n", s);
	const int32_t shift = 2;
	int32_t right_move_times = 0;
	while (temp>0)
	{
		printf("二进制 FOR right move %04d times --> %s\n",right_move_times,  s);
		temp = temp >> shift;
		right_move_times++;
		itoa(temp, s, 2);
	}
	itoa(temp, s, 3);
	printf("三进制 --> %s\n", temp);
	printf("%b\n", temp);

}
//////////////////////////////////////////////////////////////////////////




ComponentBase* NewComponent(ComponentType t, int  _input_dim, int _output_dim) {
	if (_input_dim <= 0 || _output_dim <= 0) {
		return nullptr;
	}
	ComponentBase* ans = nullptr;
	switch (t)
	{
	case ComponentType::kComponentGRU:
		ans = new GruComponent(_input_dim, _output_dim);
		break;
	case ComponentType::kComponentBN:
		ans = new BatchNormComponent(_input_dim, _output_dim);
		break;
	case ComponentType::kComponentCNN:
		ans = new Conv1DComponent(_input_dim, _output_dim);
		break;
	case ComponentType::kComponentUNK:
		break;
	default:
		//std::cerr << "ERROR COMPONENT TYPE !\nType: " << reinterpret_cast<ComponentType>(t) << std::endl;
		break;
	}
	return ans;
}






//read gru network in a predefined textual format 

const std::string MathAlorithms::gru_network_config = "3_layers_gru_network.config";



void MathAlorithms::GruNnetInit(const char* nnetwork_config) {
	using namespace std;
	ifstream nnet_is(nnetwork_config, ios::in);
	try
	{
		std::string this_line, next_token;
		ostringstream string_os;
		while (std::getline(nnet_is, this_line, '\n'))
		{
			if (!this_line.empty()) {
				istringstream string_is(this_line);
				while (!string_is.eof())
				{
					string_is >> next_token;
					double in_dim = 0, out_dim = 0;
					ComponentType t = StringToComponentType(next_token.c_str());
					VerifyNextToken(string_is, "<input>"); //不应该把这一层函数设计到这个部分！！！
					VerifyNextToken(string_is, "<indim>"); //应该把函数设计到component层面，也就是先确定了component对象
					ReadBasicType(string_is, &in_dim);//之后，根据其成员函数进行读取相关配置
					VerifyNextToken(string_is, "<outdim>");//这样循环才能继续！！
					ReadBasicType(string_is, &out_dim);//component是根据这一行第一个token来定的，第一个token被读入之后
					ComponentBase* ans = NewComponent(t, in_dim, out_dim);//在读取输入输出，直接生成一个component，之后
					if (ans) { //其余配置的读取可以定义在component内部
						componets_.push_back(ans);
					}



				}


			}

		}
		nnet_is.close();

	}
	catch (const std::exception& e)
	{
		nnet_is.close();
		std::cout << e.what() << std::endl;
	}

}




void MathAlorithms::GruRnnTrain() {
	std::string gru_network_config = "3_layers_gru_network.config";
	GruNnetInit(gru_network_config.c_str());
	//GruRnnForward();
	//GruRnnBackward();
	GruRnnApplyGradient();
}

void MathAlorithms::GruRnnForward(FloatMatrix* in) {

	if (in->RowNum() == 0 || in->ColNum()) {
		return;
	}

	int comp_size = componets_.size();
	std::vector<FloatMatrix> temp_in, temp_out;
	temp_in[0] = *in;
	for (int i = 0; i < comp_size; i++)
	{
		if (i > 0) {
			temp_in[i] = temp_out[i - 1];
		}
		componets_[i]->ForwardCompute(&(temp_in[i]), &temp_out[i]);
	}

}


void MathAlorithms::GruRnnBackward(FloatMatrix* in) {
	if (!in || in->RowNum() == 0 || in->ColNum() == 0) {
		return;
	}



	int comp_size = componets_.size();
	std::vector<FloatMatrix> temp_in, temp_out;
	temp_in[comp_size - 1] = *in;
	for (int i = comp_size - 1; i > 0; i--)
	{
		if (i > 0) {
			temp_in[i] = temp_out[i - 1];
		}
		componets_[i]->ForwardCompute(&(temp_in[i]), &temp_out[i]);
	}


}



void Histogram::InitFromFile(const char* data_file) {
	if (!data_file) {
		return;
	}
	ifstream is(data_file, ios::in);
	std::vector<int> temp_v;
	std::string next_token;
	if (is.is_open()) {
		while (!EatWs(is))
		{
			is >> next_token;
			if (!next_token.empty()) {
				temp_v.push_back(std::atoi(next_token.c_str()));
			}
		}
		is.close();
	}
	int v_size = temp_v.size();
	data_ = new int[v_size];
	std::copy(temp_v.begin(), temp_v.end(), data_);
	len_data_ = v_size;
}



//////////////////////////////////////////////////////////////////////////

void DSTest(const char* init_cfg) {
	if (init_cfg == nullptr){
		return;
	}

	StructOperations so;
	MutualNode a, b;
	MutualNode* a_p = &a, *b_p = &b;
	so.SwapAddrs(&a_p, &b_p);
	so.InitTree(init_cfg);
	so.InitList(init_cfg);
	so.BirectionList2BinaryTree();
	so.BinaryTree2BirectionList();

}


void BlockQueueTest() {

	BlockQueue q;
	q.Init(8, 8);
	char* static_ptr = "scienfic";
	q.PushBack(static_ptr);
	char* get_result = q.GetBlock(2);


}
void BlockShaperTest() {
	BlockShaper bs;
	int after_len = 4;
	bs.Init(8, 8);
	char* feed_ptr = "let's go for much better life.";
	bs.Feed(feed_ptr, after_len);
}
void ByteBufferTest() {
	int next_len = 4;
	ByteBuffer bb;
	bb.Init(1024, true);
	char* feed_ptr = "let's go for much better life.";

	bb.Feed(feed_ptr, next_len);
	bb.Shift(2);
	bb.GetByteNum();

}


void BasicDataStructure()
{
	BlockQueueTest();
	BlockShaperTest();
	ByteBufferTest();
	
}



void TestMutale(const SmallNode* in) {
	const SmallNode* this_in = in;
	this_in->Returni();
	this_in->counter_++;


	SmallNode* this_in2 = const_cast<SmallNode*>(in);
	this_in2->k++;
	this_in2->test2();

}